package com.example.demo.arithmetic.algorithm.dynamic_programing;

import com.example.demo.arithmetic.algorithm.greedy.bag.BagProblem;

import java.util.Arrays;

/**
 * 贪心算出来的并不对
 * 0 1背包问题,要么拿 要么不拿，不能只拿一部分，这是和分数背包最大的区别
 */
/*
取出10g  求取出物品的最大价值
编号  重量(g)       价值                      简称
1       4           1600        黄金一块        A
2       8           2400        红宝石一粒      R
3       5           30          白银一块        S
4       1           1_000_000   钻石一粒        D
 */
/*
   0    1   2   3   4   5   6   7   8   9   10  背包容量
0  0    0   0   0   A   A   A   A   A   A   A
1  0    0   0   0   A   A   A   A   R   R   R
2  0    0   0   0   A   A   A   A   R   R   R
4  0    D   D   D   D   A+D A+D A+D A+D R+D R+D
物品编号
    if(装不下){
    dp[i][j]=dp[i-1][j]
    }else{
    // 装得下
    dp[i][j]=Math.max(dp[i-1][j],R)  dp[1][8]=Math.max(dp[0][8],R)
    dp[3][5]=Math.max(dp[2][5],D+dp[2][4])

    最后
    dp[i][j]=Math.max(dp[i-1][j],item.sum+dp[i-1][j-item.weight])
    }
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        BagProblem.Item[] items = new BagProblem.Item[]{
                new BagProblem.Item(1, 4, 1600),
                new BagProblem.Item(2, 8, 2400),
                new BagProblem.Item(3, 5, 30),
                new BagProblem.Item(4, 1, 1_000_000),
        };
        System.out.println(new KnapsackProblem().maxValue2(items, 10));
    }

    public int maxValue(BagProblem.Item[] items, int targetWight) {
        int[][] dp = new int[items.length][targetWight + 1];

        BagProblem.Item item0 = items[0];
        for (int j = 0; j < targetWight + 1; j++) {
            if (j >= item0.weight) {
                dp[0][j] = item0.sum;
            } else {
                dp[0][j] = 0;
            }
        }

        for (int i = 1; i < dp.length; i++) {
            BagProblem.Item item = items[i];
            for (int j = 0; j < targetWight + 1; j++) {
                if (j < item.weight) {
                    dp[i][j] = dp[i - 1][j]; // 装不下
                } else {
                    // 装的下
                    dp[i][j] = Math.max(dp[i - 1][j], item.sum + dp[i - 1][j - item.weight]);
                }
            }
            printDp(dp);
            System.out.println();
        }
        return dp[dp.length - 1][targetWight];
    }

    /**
     * 降维 为一维数组
     *
     * @param items
     * @param targetWight
     * @return
     */
    public int maxValue2(BagProblem.Item[] items, int targetWight) {
        int[] dp = new int[targetWight + 1];

        BagProblem.Item item0 = items[0];
        for (int j = 0; j < targetWight + 1; j++) {
            if (j >= item0.weight) {
                dp[j] = item0.sum;
            } else {
                dp[j] = 0;
            }
        }

        for (int i = 1; i < items.length; i++) {
            BagProblem.Item item = items[i];
            for (int j = targetWight; j > 0; j--) {
                if (j>= item.weight) {
                    dp[j] = Math.max(dp[j], item.sum + dp[j - item.weight]);
                }
            }

            System.out.println(Arrays.toString(dp));
        }
        return dp[targetWight];
    }


    private void printDp(int[][] arr) {
        for (int[] its : arr) {
            for (int anInt : its) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}

